package Midium;

import java.util.*;
//注意：[1,4],[2,3]应合并为[1,4]而不是[1,3]
//56.合并区间
public class Solution56 {
    public int[][] merge(int[][] intervals) {
        //0和1，则返回自身
        if (intervals.length<=1)
            return intervals;
        //先排序
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
        for (int i = 0; i < intervals.length; i++) {
            //注意 TreeMap只允许相同的key只有一个，因此如果新的key对应的value大，则更新，否则不更新
            if(map.containsKey(intervals[i][0])&&intervals[i][1]<map.get(intervals[i][0]))
                continue;
            map.put(intervals[i][0], intervals[i][1]);
        }
        //使用set的迭代器来遍历map
        Set<Integer> keySet = map.keySet();
        Iterator<Integer> iterator = keySet.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            intervals[i][0] = iterator.next();
            intervals[i][1] = map.get(intervals[i][0]);
            i++;
        }
        //开始合并区间
        List<Integer[]> list = new ArrayList<>();
        i = 0;
        while (i < intervals.length-1) {
            if(intervals[i][1]>=intervals[i+1][0]){
                Integer[] arr = new Integer[2];
                arr[0]=intervals[i][0];
                int max = intervals[i+1][1]>intervals[i][1]?intervals[i+1][1]:intervals[i][1];
                arr[1]= max;
                i++;
                while (i < intervals.length-1 && max>=intervals[i+1][0]){
                    arr[1]=intervals[i+1][1]>arr[1]?intervals[i+1][1]:arr[1];
                    i++;
                    //更新max
                    max = arr[1];
                }
                list.add(arr);
                i++;
            }
            else {
                list.add(new Integer[]{intervals[i][0],intervals[i][1]});
                i++;
            }
        }
        //最后看一下intervals[intervals.length-1][1]这个数是不是大于list中最后一个数组的第二个数，如果大于的话，则加入
        if(list.get(list.size()-1)[1] < intervals[intervals.length-1][1]){
            list.add(new Integer[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]});
        }

        int[][] resArr = new int[list.size()][2];
        for(i=0;i<list.size();i++){
            resArr[i][0]=list.get(i)[0];
            resArr[i][1]=list.get(i)[1];
        }
        return resArr;
    }

    public static void main(String[] args) {
        Solution56 s = new Solution56();
        int[][] merge = s.merge(new int[][]{{2,3},{3,4},{4,6},{5,7}});
        for(int[] arr : merge){
            System.out.print("[");
            for (int a : arr){
                System.out.print(a+",");
            }
            System.out.print("],");
        }
    }
}
